Euclidean Algorithm
Module 02 / Lesson 02
Detailed Process Video
Finding the Greatest Common Divisor
The Euclidean Algorithm is an ancient and elegant method for finding the Greatest Common Divisor (GCD) of two numbers. It works by repeatedly dividing the larger number by the smaller one and taking the remainder until the remainder becomes zero.
The Basic Process:
To find GCD(a, b) where a ≥ b:
1. Divide a by b to get remainder r.
2. If r = 0, then b is the GCD.
3. If r > 0, repeat the process with b and r.
Core Rules:
- Replace the larger number with the smaller number in each step.
- Replace the smaller number with the remainder.
- The last non-zero remainder is the GCD.
Python Implementation (Iterative)
def find_gcd(a, b):
while b != 0:
# a becomes b, b becomes the remainder (a % b)
a, b = b, a % b
return a
# Example Trace: GCD(48, 18)
# 48 % 18 = 12 -> (18, 12)
# 18 % 12 = 6 -> (12, 6)
# 12 % 6 = 0 -> (6, 0)
# GCD is 6
num1, num2 = 48, 18
print(f"The GCD of {num1} and {num2} is: {find_gcd(num1, num2)}")